#! /usr/bin/env python
# -*- coding: utf-8 -*-

# *************************************************************
#     Filename @  sorts.py
#       Author @  Huoty
#  Create date @  2016-01-26 15:22:33
#  Description @
# *************************************************************

from random import randint

# Script starts from here

def get_list_randint(list_len, a, b):
    list_rand = []
    count = list_len
    while True:
        list_rand.append(randint(a, b))
        if count == 1:
            break;
        count -= 1

    return list_rand

def insert_sort(lists):
    list_len = len(lists)
    for i in range(1, list_len):
        uptake = lists[i]  # 表示我抽取出来要插入的数据
        j = i - 1
        # i 之前为已经排好序的数据，i 之后为待排序的数据
        while j >= 0:
            if lists[j] > uptake:
                lists[j], lists[j + 1] = uptake, lists[j]
            j -= 1

    return lists

# def shell_sort

def bubble_sort(lists):
    list_len = len(lists)
    for i in range(0, list_len - 1):
        for j in range(0, list_len - i - 1):
            if lists[j] > lists[j + 1]:
                lists[j], lists[j + 1] = lists[j + 1], lists[j]

    return lists

def __quick_sort_one(lists, left, right):
    if left >= right:
        return lists

    i = left
    j = right
    while i < j:
        while i < j and lists[j] >= lists[left]:  # 将第一个元素作为哨兵
            j -= 1
        while i < j and lists[i] <= lists[left]:
            i += 1

        if i < j:
            lists[i], lists[j] = lists[j], lists[i]

    lists[i], lists[left] = lists[left], lists[i]
    __quick_sort_one(lists, left, i - 1)
    __quick_sort_one(lists, i + 1, right)

    return lists

def quick_sort(lists):
    return __quick_sort_one(lists, 0, len(lists) - 1)

def select_sort(lists):
    lists_len = len(lists)
    for i in range(0, lists_len - 1):
        minimum = i
        for j in range(i + 1, lists_len):
            if lists[minimum] > lists[j]:
                minimum = j
        lists[i], lists[minimum] = lists[minimum], lists[i]

    return lists

def __merge_lists(left, right):
    left_len, right_len = len(left), len(right)
    i, j = 0, 0
    merge_result = []

    while i < left_len and j < right_len:
        if left[i] <= right[j]:
            merge_result.append(left[i])
            i += 1
        else:
            merge_result.append(right[j])
            j += 1

    merge_result += left[i:]
    merge_result += right[j:]

    return merge_result

def merge_sort(lists):
    lists_len = len(lists)
    if lists_len <= 1:
        return lists

    mid = lists_len // 2
    left = merge_sort(lists[:mid])
    right = merge_sort(lists[mid:])
    return __merge_lists(left, right)


if __name__ == "__main__":
    print "\n-------------------- Insert sort --------------------"
    lists = get_list_randint(10, 0, 100)
    print "Sort before: ", str(lists)
    print " Sort after: ", str(insert_sort(lists))

    print "\n-------------------- Bubble sort --------------------"
    lists = get_list_randint(10, 0, 100)
    print "Sort before: ", str(lists)
    print " Sort after: ", str(bubble_sort(lists))

    print "\n-------------------- Quick sort --------------------"
    lists = get_list_randint(10, 0, 100)
    print "Sort before: ", str(lists)
    print " Sort after: ", str(quick_sort(lists))

    print "\n-------------------- Select sort --------------------"
    lists = get_list_randint(10, 0, 100)
    print "Sort before: ", str(lists)
    print " Sort after: ", str(select_sort(lists))

    print "\n-------------------- Merge sort --------------------"
    lists = get_list_randint(10, 0, 100)
    print "Sort before: ", str(lists)
    print " Sort after: ", str(merge_sort(lists))
